package com.shuo.dsa.leetcode;

import com.shuo.dsa.model.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 后序遍历(单栈版)
 *      模仿先序: root->左->右  最后reverse整个结果
 */
public class BinTreePostOrder {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return new ArrayList<>();
        ArrayList<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            ret.add(node.value);
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        reverse(ret);
        return ret;
    }

    private void reverse(List<Integer> list) {
        int lo = 0;
        int hi = list.size() - 1;
        while (lo < hi) {
            int temp = list.get(lo);
            list.set(lo, list.get(hi));
            list.set(hi, temp);
            lo++;
            hi--;
        }
    }
}
